# -*- coding: utf-8 -*-
# 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

# 示例:
# 输入: [-2,1,-3,4,-1,2,1,-5,4],
# 输出: 6

# 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6

# 进阶:
# 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解








# 解题思路：
# 1、运用动态规划的思想，把问题分成2个部分 [0] [...]
#   如果[0] > 0说明对[...]是增益的效果，需保留
#   如果[0] < 0说明对[...]是无增益效果，需舍弃并归0
# 2、下标[0]处理完成后，得到了一个 >= 0的增益效果，然后再把余下的分为2个部分
#   重复上面的步骤
# 
# 思路的误区：
# 是否存在一种情况，有一个极大的数字[5] = 100，他会把[0,5]修正成正数，进行[0,6]的求和
# 而实际情况是[5,6]才是和最大的选项
# 按照上面的解题思路，这个问题是不存在的
# 因为在和[5]相加时，算法是保证了 [0,4] >= 0的，因而不存在[5,6] > [0,6]这种情况

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0;

        rtn = nums[0];
        total = 0;

        for i in range(len(nums)):
            total += nums[i];
            if total > rtn:
                rtn = total;
            if total < 0:
                total = 0;

        return rtn;

t = Solution();
print t.maxSubArray([-2,1,-3,4,-1,2,1,-5,4]);